package offer.offer03;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 知识: PriorityQueue 小根堆
 * peek, 只返回根, 不做操作, 失败时null;
 * poll, 删除栈顶元素并返回, 为空时返回null;
 * remove, 删除栈顶无返回, 失败时null;
 */
public class Solution41_2 {
    Queue<Integer> A, B;
    public Solution41_2() {
        A = new PriorityQueue<>(); // 小根堆，保存较大的一半
        //根据默认的Comparator, PriorityQueue是一个小根堆,
        //通过创建时传递一个反着的Comparator, 就可以变成一个大根堆
        B = new PriorityQueue<>((x, y) -> (y - x));
    }

    /**
     * 太强了……这个A.size() != B.size()的判断是为了让add操作在两个堆之间交替进行,
     * AB size相等的时候, 表明插入的是偶数个值, 不等即为奇数
     * 在往小根堆中插入值后, 把小根堆poll出最小值给大根堆, 大根堆插入值后poll出最小值给小根堆
     * 所以小根堆储存的是较大的那一半数, 大根堆是较小的
     */
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        //按照实际的增长顺序, 是先小根堆再大根堆, 交替。奇数则peek小根堆
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

